package com.atguigu.main.sort;

import java.util.Arrays;

/**
 * 希尔排序算法
 *
 * @Author 剧情再美终是戏
 * @Date 2019/12/27
 * @return
 * @Version 1.0
 **/
public class HillSort {

    /**
     * 希尔排序算法-交换法
     *
     * @param arrays
     * @return int[]
     * @Author 剧情再美终是戏
     * @Date 2019/12/27
     * @Version 1.0
     **/
    public static int[] hillSortReplace(int[] arrays) {
        long startTime = System.currentTimeMillis();
        int length = arrays.length;
        int tmp = 0;
        // 计算排序的组数
        for (int step = length / 2; step > 0; step /= 2) {
            for (int i = step; i < length; i++) {
                for (int j = i - step; j >= 0; j -= step) {
                    if (arrays[j] > arrays[j + step]) {
                        tmp = arrays[j];
                        arrays[j] = arrays[j + step];
                        arrays[j + step] = tmp;
                    }
                }
            }
        }
        System.out.printf("希尔交换排序算法\t耗时%dms\n", System.currentTimeMillis() - startTime);
        return arrays;
    }

    public static int[] hillSortMove(int[] arrays) {
        long startTime = System.currentTimeMillis();
        // 计算排序的组数
        int length = arrays.length;
        // 计算组数,每次除2
        for (int step = length / 2; step > 0; step /= 2) {
            // 从step位置开始循环
            for (int i = step; i < length; i++) {
                int j = i;
                int tmp = arrays[j];
                // 与步长为step的元素进行比较,如果发现有比它大的,就开始进入循环,将大的元素依次后移step个单位
                if (arrays[j] < arrays[j - step]) {
                    while (j - step >= 0 && tmp < arrays[j - step]) {
                        arrays[j] = arrays[j - step];
                        j -= step;
                    }
                    if (arrays[j] != tmp) {
                        arrays[j] = tmp;
                    }
                }
            }
        }
        System.out.printf("希尔移动排序算法\t耗时%dms\n", System.currentTimeMillis() - startTime);
        return arrays;
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 2, 4, 9, 8};
        System.out.println(Arrays.toString(HillSort.hillSortMove(array)));
    }

}
